from typing import List

class Solution:
    def pancakeSort(self, arr: List[int]) -> List[int]:
        """
        煎饼排序算法
        使用煎饼翻转完成对数组的排序
        """
        ans = []
        for n in range(len(arr), 1, -1):
            index = 0
            for i in range(n):
                if arr[i] > arr[index]:
                    index = i
            if index == n - 1:
                continue
            m = index
            for i in range((m + 1) // 2):
                arr[i], arr[m - i] = arr[m - i], arr[i]  # 原地反转
            for i in range(n // 2):
                arr[i], arr[n - 1 - i] = arr[n - 1 - i], arr[i]  # 原地反转
            ans.append(index + 1)
            ans.append(n)
        return ans

def simple_pancake_sort(arr: List[int]) -> List[int]:
    """简化版煎饼排序，用于验证"""
    def flip(arr, k):
        """翻转前k个元素"""
        left, right = 0, k - 1
        while left < right:
            arr[left], arr[right] = arr[right], arr[left]
            left += 1
            right -= 1
    
    result = []
    n = len(arr)
    
    for i in range(n, 0, -1):
        # 找到当前范围内最大的元素
        max_idx = 0
        for j in range(i):
            if arr[j] > arr[max_idx]:
                max_idx = j
        
        # 如果最大元素不在正确位置，进行翻转
        if max_idx != i - 1:
            if max_idx != 0:
                flip(arr, max_idx + 1)
                result.append(max_idx + 1)
            flip(arr, i)
            result.append(i)
    
    return result

def test_algorithm():
    """测试算法"""
    solution = Solution()
    
    # 测试用例
    test_cases = [
        ([3, 2, 4, 1], [4, 2, 4, 3]),
        ([1, 2, 3], []),
        ([2, 1], [2]),
        ([1], []),
        ([3, 1, 2], [3, 2])
    ]
    
    print("算法测试结果:")
    print("=" * 30)
    
    for arr, expected in test_cases:
        # 创建数组副本
        arr_copy = arr.copy()
        result = solution.pancakeSort(arr_copy)
        
        # 验证结果
        is_valid = len(result) <= 10 * len(arr) and is_sorted(arr_copy)
        status = "✓" if is_valid else "✗"
        
        print(f"{status} 输入: {arr}")
        print(f"    输出: {result}")
        print(f"    排序后: {arr_copy}")
        print(f"    期望: {expected}")
        print()

def is_sorted(arr: List[int]) -> bool:
    """检查数组是否已排序"""
    for i in range(1, len(arr)):
        if arr[i] < arr[i-1]:
            return False
    return True

if __name__ == "__main__":
    test_algorithm() 